61. Rotate List

題目

Given the head of a linked list, rotate the list to the right by k places.

Example 1:

Input: head = [1,2,3,4,5], k = 2
Output: [4,5,1,2,3]

Example 2:

Input: head = [0,1,2], k = 4
Output: [2,0,1]

Constraints:

• The number of nodes in the list is in the range [0, 500].
• 100 <= Node.val <= 100
• 0 <= k <= 2 * 10^9

解法(Java)

這題看起來沒有很難，但實際上也解了快兩個小時，解法是要算一下往右移動k個位置，現在的開頭會在哪裡，新的開頭又是哪裡。

但算一下之後發現到k其實可以當作刪除後面幾個元素補到前面去，如果k大於鏈結陣列長度的話，就除以它取餘數作為新的k，這樣就可以解出來了。

Runtime: 0 ms (100%)
Memory Usage: 41.3 MB (44.99%)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode rotateRight(ListNode head, int k) {
    	if (head == null || head.next == null || k == 0) return head;
    	
    	ListNode fast = head;
    	int counter = 0;
    	while (fast != null && counter != k) {
    		fast = fast.next;
    		counter++;
    	}
    	
    	if (fast == null && counter == k) return head;
    	
    	if (fast == null && counter != k) {
    		fast = head;
        	counter = k % counter;
        	if (counter == 0) return head;
        	while (counter > 0) {
        		fast = fast.next;
        		counter--;
        	}
    	}
    	
    	ListNode slow = head;
    	ListNode slowPrev = null;
    	ListNode fastPrev = null;
    	while (fast != null) {
    		fastPrev = fast;
    		fast = fast.next;
    		slowPrev = slow;
    		slow = slow.next;
    	}
    	
    	if (fastPrev != null) fastPrev.next = head;
    	if (slowPrev != null) slowPrev.next = null;
    	
        return slow;
    }
}

小結

最近工作量真的挺多的，這題目用了四個pointer解題，導致記憶體用量暴增，實際上應該可以再減少兩個pointer，但等有空的時候再去想吧~~